#include <iostream>
#include <string>

using namespace std;

void reverse(string &s, int start, int end)
{
    for(int i = start, j = end - 1; i < j; i++, j--)
    {
        swap(s[i], s[j]);
    }
}

class Solution 
{
public:
    string reverseWords(string s) 
    {
        int slow = 0;
        for(int fast = 0; fast < s.size(); fast++)
        {
            if(s[fast] != ' ')
            {
                if(slow != 0)
                {
                    s[slow] = ' ';
                    slow++;
                }
                while(fast < s.size() && s[fast] != ' ')
                {
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }
            }
        }

        s.resize(slow);

        reverse(s, 0, s.size());
        int start = 0;
        for(int i = 0; i <= s.size(); i++)
        {
            if(s[i] == ' ' || i == s.size())
            {
                reverse(s, start ,i);
                start = i + 1;
            }
        }
        return s;
    }
};

int main()
{
    Solution sol;

    // 测试用例1
    string s1 = "the sky is blue";
    cout << "输入: \"" << s1 << "\"" << endl;
    cout << "输出: \"" << sol.reverseWords(s1) << "\"" << endl;
    // 期望输出: "blue is sky the"

    // 测试用例2
    string s2 = "  hello world  ";
    cout << "输入: \"" << s2 << "\"" << endl;
    cout << "输出: \"" << sol.reverseWords(s2) << "\"" << endl;
    // 期望输出: "world hello"

    // 测试用例3
    string s3 = "a good   example";
    cout << "输入: \"" << s3 << "\"" << endl;
    cout << "输出: \"" << sol.reverseWords(s3) << "\"" << endl;
    // 期望输出: "example good a"

    // 测试用例4
    string s4 = "  Bob    Loves  Alice   ";
    cout << "输入: \"" << s4 << "\"" << endl;
    cout << "输出: \"" << sol.reverseWords(s4) << "\"" << endl;
    // 期望输出: "Alice Loves Bob"

    // 测试用例5
    string s5 = "Alice does not even like bob";
    cout << "输入: \"" << s5 << "\"" << endl;
    cout << "输出: \"" << sol.reverseWords(s5) << "\"" << endl;
    // 期望输出: "bob like even not does Alice"

    return 0;
}
